#include<stdio.h>
#include<stdlib.h>
#include <string.h>

#define XALLOC(type,size) (type *)malloc(size*sizeof(type))
#define XMEMSET(pointer,type,num) memset(pointer,0,num*sizeof(type))

typedef struct treeNode
{
	struct treeNode *left;
	struct treeNode *right;
	struct treeNode *parent;
	int node;
}TreeNode;

void AssignNode(TreeNode *node,int content)
{
	node->node = content;
	node->right = NULL;
	node->left = NULL;
	node->parent = NULL;
}

void BuildTree(TreeNode *node,int content)
{
	if(node != NULL)
	{
		if(node->node>content)
		{
			if(node->left!=NULL)
				BuildTree(node->left,content);
			else
			{
				node->left = XALLOC(TreeNode,1);
				AssignNode(node->left,content);
				node->left->parent = node;
			}
		}
		else
		{
			if(node->right!=NULL)
				BuildTree(node->right,content);
			else
			{
				node->right = XALLOC(TreeNode,1);
				AssignNode(node->right,content);
				node->right->parent = node;
			}
		}
	}
}

void DumpTree(TreeNode *root)
{
	if(root!=NULL)
	{
		DumpTree(root->left);
		printf("%d\t",root->node);
		DumpTree(root->right);
	}
}

TreeNode* MaxNode(TreeNode *root)
{
	if(root->right==NULL)
	{
		printf("%d\n",root->node);
		return root;
	}

	if(root->right!=NULL)
	{
		MaxNode(root->right);
	}
}

TreeNode* MinNode(TreeNode *root)
{
	if(root->left == NULL)
	{
		printf("%d\n",root->node);
		return root;
	}

	if(root->left!=NULL)
	{
		MinNode(root->left);
	}
}

TreeNode* SearchNode(TreeNode* root,int target)
{
	if(root->node == target)
	{
		return root;
	}

	if(root->node>target)
	{
		if(root->left!=NULL)
		{
			return SearchNode(root->left,target);
		}
		else
			return NULL;
	}

	if(root->node<target)
	{
		if(root->right!=NULL)
		{
			return SearchNode(root->right,target);
		}
		else
			return NULL;
	}

	return NULL;
}

TreeNode *TreeSuccessor(TreeNode *root)
{
	return MinNode(root->right);
}

TreeNode *TreePreccessor(TreeNode *root)
{
	return MaxNode(root->left);
}

void DeleteNode(TreeNode* root,int target)
{
	TreeNode* targetNode = SearchNode(root,target);
	if(targetNode != NULL)
	{
		TreeNode* pointNode; //Point to Delete Node
		if(targetNode->left == NULL || targetNode->right == NULL)
		{
			pointNode = targetNode;
		}
		else
			pointNode = TreeSuccessor(targetNode);

		//pointNode points to the node to be deleted.
		/*If pointNode is not the node we want to delete, we need to move the 
		* successor, so we need to delete the successor as well.
		*/
		TreeNode *nextNode;
		if(pointNode->left != NULL)
		{
			nextNode= pointNode->left;
		}
		else
		{
			nextNode = pointNode->right;
		}

		if (nextNode != NULL)
		{
			nextNode->parent = pointNode->parent;
		}

		if(pointNode->parent==NULL)
		{
			root->node = nextNode->node;
		}
		else
		{
			if(pointNode->parent->left == pointNode)
			{
				pointNode->parent->left = nextNode;
			}

			if(pointNode->parent->right == pointNode)
			{
				pointNode->parent->right = nextNode;
			}
		}

		if(targetNode != pointNode)
		{
			targetNode->node = pointNode->node;
		}
	}
	else
		printf("The node does not exists\n");
}

int main() 
{
	int a[9]={1, 4, 5, 10, 16, 17, 21,-3,-1};
	int i;

	TreeNode *root= XALLOC(TreeNode,1);
	AssignNode(root,a[0]);

	for(i=1;i<9;i++)
	{
		BuildTree(root,a[i]);
	}

	DumpTree(root);

	printf("\n");
	MaxNode(root);
	printf("\n");
	MinNode(root);
	printf("\n");

	TreeNode *result = SearchNode(root,5);

	if(result!=NULL)
	{
		printf("%d exists",result->node);
	}

	printf("\n");
	printf("\n");

	for(i=1;i<9;i++)
	{
		printf("Delete Node %d\n",a[i]);
		DeleteNode(root,a[i]);
		DumpTree(root);
		printf("Delete End!!\n");
	}

	return 0; 
} 
